package com.leetcode.practice.quesions;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import com.leetcode.practice.interfaces.IQuestion;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

	示例 1:

	输入: "abcabcbb"
	输出: 3 
	解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
	示例 2:

	输入: "bbbbb"
	输出: 1
	解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
	示例 3:

	输入: "pwwkew"
	输出: 3
	解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
	     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author Administrator
 *
 */
public class q2_无重复字符最长字符串 implements IQuestion {

	String str="bbbbb";

	@Override
	public void solution() {
		// TODO Auto-generated method stub
		//		solution2();
		solution3();
	}


	/**
	 * 暴力破解法
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(1)
	 */
	private void solution1() {
		int maxLength=0;
		for(int i=0;i<str.length()-1;i++) {
			for(int j=i+1;j<str.length();j++) {
				if(str.charAt(j)==str.charAt(i)) {
					int length=j-i;
					if(length>maxLength) {
						maxLength=length;
					}
					break;
				}
			}
		}
		System.out.println("最长字符串长度->"+maxLength);
	}

	/**
	 * 滑动窗口法破解
	 * 
	 * 时间复杂度：O(2n)=O(n)
	 * 空间复杂度：O(n)
	 */
	private void solution2() {
		Set<Character> set = new HashSet();
		int maxLength=0;
		int i=0,j=0;
		while(i<str.length() && j<str.length()) {
			if(!set.contains(str.charAt(j))) {
				set.add(str.charAt(j++));
				maxLength=Math.max(maxLength, j-i);
			}else {
				set.remove(str.charAt(i++));
			}
			System.out.println("i->"+i+",j->"+j);
		}
		System.out.println("最长字符串长度->"+maxLength+",set->"+set.toString());
	}

	/**
	 * 滑动窗口优化 
	 * 
	 * 时间复杂度：O(n)
	 * 空间复杂度：O(n)
	 */
	private void solution3() {
		int maxLength=0;
		Map<Character,Integer> map=new HashMap();
		for(int i=0,j=0;j<str.length();j++) {
			if(map.containsKey(str.charAt(j))){
				i=j;
			}
			map.put(str.charAt(j), j);
			maxLength=Math.max(maxLength, j-i+1);
		}
		System.out.println("最长字符串长度->"+maxLength+",map->"+map.toString());
	}


	public static void main(String[] args) {
		q2_无重复字符最长字符串 q2=new q2_无重复字符最长字符串();
		q2.solution();
	}
}
